# This compares implementations of merge sort and insert sort.
# It assumes insertion sort runs in 8n^2 steps while merge
# runs in 64nlogn steps.

import math

# We start at 2 as log of 1 to any base is always zero and 
# we must rule out that case.
_START_VALUE = 2
_MAX_VALUE = 100000

def main():
  for n in xrange(_START_VALUE, _MAX_VALUE):
    insert = 8 * pow(n, 2)
    merge = 64 * n * math.log(n, 2)
  
    if merge < insert:
      print 'At n=%r merge is more efficient than insert.' % (n)
      print 'Merge: %r Insert: %s.' % (merge, insert) 
      break

if __name__ == "__main__":
  main()
